/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2025-08-14
 * Time: 23:30
 */
public class Test81 {
//    public static int jump(int[] num) {
//        int n = num.length;
//        int left = 0, right = 0, maxIndex = 0,ret = 0;
//        while(left <= right) {
//            if(maxIndex >= n-1) {
//                return ret;
//            }
//            for(int i = left; i <= right; i++) {
//                maxIndex = Math.max(num[i]+i,maxIndex);
//            }
//            ret++;
//            left = right+1;
//            right = maxIndex;
//        }
//        return -1;
//    }

    public static int jump(int[] num) {
        int n = num.length;
        int[] dp = new int[n];
        dp[0] = 0;
        for(int i = 1; i < n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for(int j = i-1; j >= 0; j--) {
                if(num[j]+j >= i) {
                    dp[i] = Math.min(dp[i],dp[j]+1);
                }
            }
        }
        return dp[n-1];        
    }

    public static void main(String[] args) {
        int[] num = {2,3,1,1,4};
        int ret = jump(num);
        System.out.println(ret);
    }
}
